A directed, weighted graph with a self-loop

  • Graph D is a directed, weighted graph with vertex set V = {A, B, C} and four directed edges. Each edge has an associated weight representing cost, distance, or capacity depending on the application context.
  • The edges are: A→B with weight 3, B→C with weight 2, C→A with weight 5, and a self-loop A→A with weight 1. The self-loop represents a connection from vertex A back to itself, which is valid in directed graphs.
  • Unlike undirected graphs, directed edges are asymmetric: an edge from A to B does not imply an edge from B to A. In this example, there's an edge A→B but no edge B→A, creating a one-way relationship between these vertices.
  • The presence of weights and direction makes this graph more complex to represent than undirected, unweighted graphs. In the next slide, we'll see how to encode this structure using edge lists, adjacency lists, and adjacency matrices while preserving both direction and weight information.